arxiv：2502.02572V1 [CS.DS] 2025年2月4日__

arxiv：2502.02572V1 [CS.DS] 2025年2月4日

可下载资源数量

已经购买

下载数量：1

单价	0 3.0
Coupon	100% 0%
Total	0 3.0

点击下载点击购买并下载

点击购买，资源将自动在新窗口打开.

机构名称：

arxiv：2502.02572V1 [CS.DS] 2025年2月4日

¥ 3.0

热度

摘要。连接的图具有（k，ℓ） - 覆盖，如果其每个边都包含在至少在k级的cliques中。以极端组合学的最新进展和边缘修改问题的文献的推动，我们研究了（k，ℓ） - 结构问题的算法版本。给定连接的图G，（k，ℓ） - 覆盖问题是识别g的最小子集，以使其在g中添加的添加结果会导致具有A（k，ℓ）覆盖的图形。对于每个常数k≥3，我们表明（k，1） - 覆盖问题是通用图的NP综合。此外，我们表明，对于每个常数k≥3，（k，1）cover问题承认，除非p = np，否则不接受多项式时间恒定因子近似算法。但是，我们表明（3，1） - 覆盖问题可以在输入图是和弦时在多项式时间内解决。对于树的类别和K的一般值，我们表明（K，1） - 覆盖概率是NP-HARD，即使对于蜘蛛也是如此。但是，我们表明，对于每个k≥4，（3，k-2） - 覆盖和（k，1） - 跨性问题是恒定的，当输入图是树是一棵树时。关键字：计算复杂性，图形算法，最佳算法，边缘修改问题和近似算法。

添加pdf代下载 VIP点击下载文件